#include <iostream>

struct ListNode
{
    int val;
    ListNode *next;

public:
    ListNode()
    {
        val = 0;
        next = nullptr;
    }
    ListNode(int v)
    {
        val = v;
        next = nullptr;
    }
    ListNode(int v, ListNode *n)
    {
        val = v;
        next = n;
    }
};

ListNode *CreateListNodes(int arr[], int size)
{

    ListNode *head = new ListNode(arr[0]);
    ListNode *current = head;
    for (int i = 1; i < size; i++)
    {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }

    return head;
}
ListNode *MergeListNode(ListNode *head1, ListNode *head2)
{
    ListNode *head = new ListNode(0);
    ListNode *current = head;
    while (head1 != nullptr && head2 != nullptr)
    {
        if (head1->val <= head2->val)
        {
            current->next = head1;
            head1 = head1->next;
        }
        else
        {
            current->next = head2;
            head2 = head2->next;
        }
        current = current->next;

        if (head1 != nullptr)
        {
            current->next = head1;
        }
        else
        {
            current->next = head2;
        }
    }
    ListNode *result = head->next;
    return result;
}
int main()
{
    int list1[] = {1, 3, 5, 6, 9};
    int list2[] = {2, 4, 6, 7, 8};
    ListNode *temp1 = CreateListNodes(list1, sizeof(list1) / sizeof(int));
    ListNode *temp2 = CreateListNodes(list2, sizeof(list2) / sizeof(int));

    ListNode *temp = MergeListNode(temp1, temp2);
    while (temp != nullptr)
    {
        std::cout << temp->val << "->";
        temp = temp->next;
    }

    return 0;
}